#ifndef SOLVER_H
#define SOLVER_H

#include "Instance.h"
#include "State.h"

#include <stack>

using namespace std;

/*
MBG

Metoda:
BB-DFS

Vstup: 
n = prirozene cislo predstavujici pocet uzlu grafu, n ≥ 5
k = prirozene cislo radu jednotek predstavujici stupen uzlu grafu G
G(V,E) = neorietovany neohodnoceny k-regularni graf o n uzlech

Cena:
počet barev
dolni mez = ?			- nevime kolik bude mit optimalni reseni
tesna dolni mez = 2		- urcite to bude vic nez 2
trivialni horni mez = k+1

Hloubka:
n


Sekvencni algoritmus:

Reseni vzdy existuje. Sekvencni algoritmus je typu BB-DFS s omezenou hloubkou prohledavaneho prostoru. Stav je dan castecny obarvenim. Mezistav ci koncovy stav je pripustny, jestlize zadne 2 sousedni uzly nejsou obarvene stejnou barvou. Navrat provadime, pokud nelze zadny uzel pridat, aniz by se porusila podminka barevnosti.

Trivialni horni mez predstavuje obarveni grafu k+1 barvami (kazdy k-regularni graf lze uzlove obarvit k+1 barvami).

Tesna spodni mez je 2. Pokud je G bipartitni, existuje obarveni dvema barvami.

*/

class Solver {
  private:
    Instance* pInstance;    //pointer na instanci grafu
    stack<State> pStates;   //stack na stavy
    State pState;           //nejlepsi reseni
    long pCounter;
    time_t pElapsed;
  public: //lifetime
    Solver(Instance* aInstance);
    ~Solver();
  public: //own methods
    State& solve();         //metoda na reseni
    time_t getElapsed();     //vrátí délku trvání výpočtu
    long getCount();         //vrátí počet expandovaných stavů
};

#endif
// vim: ts=2 fdm=marker syntax=cpp expandtab sw=2
